package com.whosly.demo.benchmark.sortalgorithms.counting;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

/**
 * 计数排序（Counting Sort）
 *
 * @author fengyang
 * @date 2023/6/13 上午11:38
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class CountingSort implements ISortingAlgorithms
{
    @Override
    public int[] sorting(int[] arr)
    {
        int len = arr.length;
        if (len < 2) {
            return arr;
        }

        int minVal = arr[0], maxVal = arr[0];
        for (int i = 1; i < len; i++) {
            if (arr[i] < minVal) {
                minVal = arr[i];
            } else if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }

        int[] countArr = new int[maxVal - minVal + 1];
        for (int val : arr) {
            countArr[val - minVal]++;
        }
        for (int arrIdx = 0, countIdx = 0; countIdx < countArr.length; countIdx++) {
            while (countArr[countIdx]-- > 0) {
                arr[arrIdx++] = minVal + countIdx;
            }
        }

        return arr;
    }
}
